package code2101_2200.code60_70;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 找出数组中重复的数字。
 *
 *
 * 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，
 * 也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
 *
 * 输入：
 * [2, 3, 1, 0, 2, 5, 3]
 * 输出：2 或 3
 */
public class _2160findRepeatNumber {

    /**
     * 空间换时间
     * 执行用时：     * 7 ms     * , 在所有 Java 提交中击败了     * 37.91%     * 的用户
     * 内存消耗：     * 47.3 MB     * , 在所有 Java 提交中击败了     * 30.91%     * 的用户
     * @param nums
     * @return
     */
    public int findRepeatNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if(set.contains(nums[i]))return nums[i];
            set.add(nums[i]);
        }
        return 0;
    }

    /**
     * 这道题在原书上绝对不是简单级别啊！
     * 它考察的是程序员的沟通能力，先问面试官要时间/空间需求！！！
     * 只是时间优先就用字典，  (set集合)
     * 还有空间要求，就用指针+原地排序数组， （指针+排序）
     * 如果面试官要求空间O(1)并且不能修改原数组，还得写成二分法！！！  （原地hash，在输出重复即可）
     *
     * 第二种方法：因为数组大小是小于数组长度n的。但会修改原数组
     * 所以我们可以让 位置i 的地方放元素i。如果位置i的元素不是i的话，那么我们就把i元素的位置放到它应该在的位置，
     * 即 nums[i] 和nums[nums[i]]的元素交换
     * @param nums
     * @return
     */
    public int findRepeatNumber1(int[] nums) {

        /**
         * 遍历数组：将数值为i的元素。找到i下标设置为-1.如果再次设为-1时，则返回此值（已经设置过一次了，重复了）
         *
         * 下一种办法是将数组原地改为原数组中的值
         * 执行用时：         * 1 ms         * , 在所有 Java 提交中击败了         * 79.34%         * 的用户
         * 内存消耗：         * 46 MB         * , 在所有 Java 提交中击败了         * 82.07%         * 的用户
         */
        int n = nums.length;
        for(int i = 0; i < n; i++){
            int k = nums[i];
            if(k < 0) k += n;
            if(nums[k] < 0) return k;
            nums[k] -= n;
        }
        return -1;
    }

}
